package recursion;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @Author wangtengyu
 * @Create 2018-03-23-14:43
 * 二分查找
 */
public class BinarySerach {

    /**
     * 非递归二分查找 找到返回数组下标 找不到返回-1
     * @param array
     * @param key
     * @return
     */
    public static int search(int[] array,int key){
        int min=0;
        int max=array.length-1;
        while (min<=max){
            int mid=(max-min)/2+min;  //等同于 (max+min)/2 防止相加越界
            if(array[mid]==key){
                return mid;
            }
            if(array[mid]>key){
                max=mid-1;
            }
            if(array[mid]<key){
                min=mid+1;
            }
        }

        return -1;
    }

    /**
     * 二分查找递归
     * @param array
     * @param key
     * @param min
     * @param max
     * @return
     */

    public static int recursiveSearch(int[] array,int key,int min,int max){
        int mid=(max-min)/2+min;
        if(key==array[mid]){
            return mid;
        }else if (min>max){
            return -1;
        }else{
            if(key>array[mid]){
                return recursiveSearch(array,key,mid+1,max);
            }
            if(key<array[mid]){
                return recursiveSearch(array,key,min,mid-1);
            }
        }
        return -1;
    }


    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int[] array={1,6,9,14,24,33,48,52,67,74,88,99};
        System.out.println("请输入要查找的数值");
        int key=scanner.nextInt();
//        int result=search(array,key);
        int result=recursiveSearch(array,key,0,array.length-1);
        System.out.println("递归查找的索引为"+result);
        System.out.println("递归查找的结果为"+array[result]);
        List list=new ArrayList();
    }

}
